#define _CRT_SECURE_NO_WARNINGS 1 

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* newhead = new ListNode(0);
        newhead->next = head;

        ListNode* begin, * end;
        begin = end = newhead;
        for (int i = 1; i <= n + 1; i++)
        {
            if (i < m)
                begin = begin->next;
            end = end->next;
        }

        ListNode* prev, * pcur, * pnext;
        prev = begin, pcur = prev->next, pnext = pcur->next;
        ListNode* tou = pcur;
        while (pnext != end)
        {
            prev = pcur;
            pcur = pnext;
            pnext = pnext->next;
            pcur->next = prev;
        }
        tou->next = end;
        begin->next = pcur;
        return newhead->next;
    }
};

int main()
{
    ListNode* head = new ListNode(1);
    ListNode ln1(2);
    ListNode ln2(3);
    ListNode ln3(4);
    ListNode ln4(5);
    head->next = &ln1;
    ln1.next = &ln2;
    ln2.next = &ln3;
    ln3.next = &ln4;
    ln4.next = nullptr;
    ListNode* pcur = head;
    while (pcur != nullptr)
    {
        cout << pcur->val << ' ';
        pcur = pcur->next;
    }
    Solution s;
    pcur = s.reverseBetween(head, 2, 4);
    while (pcur != nullptr)
    {
        cout << pcur->val << ' ';
        pcur = pcur->next;
    }

    return 0;
}